package Offer.offer2019;

import java.util.ArrayList;
import java.util.List;

import domain.TreeNode;

/**
 * 二叉树中和为某一值的路径
 * @author: leiwenkang
 * @date: 2019/5/17
 * @time: 12:56
 */
public class Offer25 {

    public static void main(String[] args) {
        TreeNode node1=new TreeNode(10);
        TreeNode node2=new TreeNode(5);
        TreeNode node3=new TreeNode(12);
        TreeNode node4=new TreeNode(4);
        TreeNode node5=new TreeNode(7);
        node1.left=node2;
        node1.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node3.right=null;
        node4.left=node4.right=null;
        node5.left=node5.right=null;

        Offer25 offer = new Offer25();
//        剑指offer.findPath(node1,22);
        System.out.println(offer.FindPath2(node1, 22));
    }

    ArrayList<ArrayList<Integer>> result = new ArrayList();
    ArrayList<Integer> path = new ArrayList();

    public ArrayList<ArrayList<Integer>> FindPath2(TreeNode root,int target) {
        if (root == null) {
            return result;
        }
        path.add(root.val);
        target -= root.val;
        boolean isLeaf = (root.left == null && root.right == null);
        if (isLeaf && target == 0) {
            result.add(new ArrayList<Integer>(path));
        }
        FindPath2(root.left, target);
        FindPath2(root.right, target);
        path.remove(path.size() - 1);
        return result;
    }

    public void findPath(TreeNode root, int target) {
        if (root == null) {
            return;
        }
        List<Integer> path = new ArrayList<>();
        findPath(root, target, path, 0);
    }

    private void findPath(TreeNode root, int target, List<Integer> path, int sum) {
        if (root == null) {
            return;
        }
        path.add(root.val);
        sum += root.val;
        //若是叶子结点，并且路径和为target，则表示已找到一条路径
        if (isLeaf(root) && sum == target) {
            printPath(path);
        }
        //若该结点有左子节点，则继续将左子节点的值加入到路径中
        if (root.left != null) {
            findPath(root.left, target, path, sum);
        }
        //若该结点有右子节点，则继续将右子节点的值加入到路径中
        if (root.right != null) {
            findPath(root.right, target, path, sum);
        }
        //将该结点移除，继续查找
        path.remove(path.size() - 1);
    }

    private boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }

    private void printPath(List<Integer> path) {
        System.out.print("找到了路径：");
        for (int i = 0; i < path.size(); i++) {
            System.out.print(path.get(i) + " ");
        }
        System.out.println();
    }
}
